1. Field of the Invention
The present invention relates to image processing, and more particularly, to a method and apparatus for compressing and decompressing image data.
2. Description of Related Art
Image processing, or picture processing, refers to a variety of techniques for manipulating pictorial information with a computer. Typically, pictorial information is collected by an analog scanning device, such as a camera or optical scanner, and input to the computer by converting the analog signals to digital signals. The analog-to-digital conversion process results in the creation of a set of numbers representing the shape and various attributes of the image.
The type of device used by computers to display images is typically a cathode-ray tube (CRT). A CRT is a device based on similar technology as that employed in television sets. Modern day CRTs typically include the capability to adjust visual attributes such as contrast and color. The resolution capability of a CRT can range from high (e.g., specialized CRTs used in film making can display as many as nine million pixels per screen), to somewhat low (e.g., 64,000 in typical computer monitor). Higher resolution capability translates into sharper, clearer images.
A digital "picture" or "image" includes elements referred to as "dots," "points" "picture elements," "pels," or "pixels." The value of an element is typically encoded as an n-bit binary number which indicates brightness (or gray level) and/or color attributes, where the value of n varies depending upon how much information is desired concerning an individual pixel. Thus, for example, in order to represent a 500.times.500 pixel image, where each pixel is represented by an 8-bit binary number, 2,000,000 bits of information would need to be stored. Fortunately, most digital images include redundant information that can be compressed without loss of information.
One compression technique involves replacing frequently occurring gray levels, or blocks of gray levels, with short codes and infrequently occurring gray levels with longer codes. Another technique relies on storing the differences between the pixel values of two adjacent lines (or columns) rather than the pixel values of the lines (or columns) themselves. Yet another technique is to represent the image by the positions (or lengths) of runs of constant gray level, or more generally, to specify the positions and shapes of regions of constant gray level.
Compression techniques in which the compressed image can be decompressed into the exact original image are referred to as "lossless" techniques, since no information is lost in the decompression process. "Lossy" compression techniques involve approximation techniques in which information is discarded in favor of reduced storage requirements. The digitization process itself is a process of approximation based on spatial sampling and gray-level quantization of a given real time image. Because of the limitations of the human visual system, lossy techniques often permit images to be displayed without any difference between the original being perceptible by the viewer.
Presently, one of the most frequently used digital image compression techniques is the Joint Photographic Experts Group (JPEG) technique. The technique is described in the International Standards Organization Committee Draft document ("Draft"), ISO/IEC CD 10918-1, which is specifically incorporated herein. JPEG is an international standards group whose goal has been to develop a general-purpose international standard for the compression of continuous-tone (gray scale or true color) digital images. A portion of the standard, referred to as the Baseline Sequential Process, has been implemented in hardware form by C-Cube Microsystems in their C-Cube CL550 JPEG Image Compression Processor. The CL550 is described in the C-Cube CL550.TM. JPEG Image Compression Processor, Preliminary Data Book, August 1991, which is specifically incorporated herein. As used herein, the term "JPEG Process" shall mean the JPEG Baseline Sequential Process, whether implemented in a computer hardware or computer software form.
The JPEG Process is a lossy technique in which there is a limit on the amount of compression that can be accomplished prior to the image quality becoming unacceptably poor. One reason the image becomes unacceptable is because the technique results in a tiling (blocking) effect which becomes visible on the screen. Beyond certain compression ratios, the JPEG Process may also result in degradation of color quality.
The details of the JPEG Process are discussed in the Draft and an exhaustive description of the process is unnecessary for understanding the present invention. In general, the Process involves three steps (a) a Discrete Cosine Transformation ("DCT"); (b) a Coefficient Quantization; and (c) a Lossless Compression.
The DCT step converts spatial information into frequency information in a lossless manner. An inverse DCT step converts frequency information into spatial information. The DCT step is performed on an N.times.N matrix of pixels and results in the creation of an N.times.N matrix of frequency coefficients. The JPEG standard calls for an 8.times.8 matrix in DCT calculations and it is this constraint which results in a disadvantageous tiling effect on displayed images beyond certain compression ratios. The tiling effect becomes apparent at a compression ratio of approximately 20:1.
The Coefficient Quantization step maps the DCT output matrix into a compressed quantization matrix. The quantization stage results in loss of information and is therefore the "lossy" phase of the JPEG Process. The amount of lost information may be regulated by setting a "quality factor" in connection with the quantization stage which typically ranges in value from 1 to 25. A low quality factor equates to low compression ratios and high picture quality, whereas a high quality factor equates to high compression ratios and low picture quality. The net effect of the quantization stage is "zero out" a number of the N.times.N entries of the DCT output matrix. Zero entries may then be handled in a uniform and compact manner resulting in compression of the image information.
The Lossless Compression step of the JPEG Process compresses the quantization matrix without loss of information. The precise manner of the compression may vary with the implementer of the JPEG standard. The basic steps are to convert the DCT coefficient at position 0,0 in the matrix to a relative value, arrange the coefficients in a "zig-zag sequence" and "Entropy Coding" of the coefficients. These steps are discussed in more detail in the Draft, and need not be further considered here.
The three JPEG Process compression steps have inverse counterparts for decoding a compressed image into a decompressed image.
__________________________________________________________________________ U.S. Pat. No. Expires Inventor Title __________________________________________________________________________ 4,224,481 09-23-1997 Russell COMPRESSION AND EXPANSION CIRCUITRY FOR A RECORDING AND PLAYBACK SYSTEM 4,320,488 03-16-1999 Russell RECORDING AND PLAYBACK SYSTEM 4,495,609 01-22-2002 Russell RECORDING AND PLAYBACK SYSTEM 4,672,443 06-09-2004 Dischert COPATIBLE WIDE SCREEN TELEVISION SYSTEM WITH IMAGE COMPRESSION EXPANDER 4,730,215 03-08-2005 Jose COMBATIBLE WIDE SCREEN TELEVISION SYSTEM WITH VARIABLE IMAGE COMPRESSION/EXPANSION 4,899,394 02-06-2007 Lee APPARATUS AND METHOD FOR IMAGE COMPRESSION 4,196,448 04-01-1997 Whitehouse TV BANDED REDUCTION SYSTEM USING A HYBRID DISCRETE COSINE DPCM 4,607,290 08-19-2003 Murakami IMAGE INFORMATION FILING APPARATUS 4,685,141 08-04-2004 Hoque METHOD AND SYSTEM FOR FINDING IMAGE DATA ASSOCIATED WITH THE MONETARY AMOUNT ON FINANCIAL DOCUMENTS 4,716,453 12-29-1997 Pawelski DIGITAL VIDEO TRANSMISSION SYSTEM 4,783,834 11-08-2005 Anderson SYSTEM FOR CREATING TRANSPOSED IMAGE DATA FROM A RUN END OR RUN LENGTH REPRESENTATION OF AN IMAGE 4,885,786 12-05-2006 Anderson METHOD FOR ENLARGING AN IMAGE STORED IN RUN REPRESENTATION FORM 4,929,937 05-29-2007 Ara CIRCUIT FOR GENERATING IMAGE SIGNAL 4,931,984 05-05-2007 Ny FILE DATA RETRIEVING SYSTEM USING RETRIEVAL-USE-IMAGE DATA 5,034,817 07-23-2008 Everett RECONFIGURABLE VIDEO LINE DIGITIZER AND METHOD FOR STORING PREDETERMINED LINES OF A COMPOSITE VIDEO SIGNAL 5,040,233 08-13-2008 Davy DATA COMPRESSION BY DISCARDING PORTIONS OF DATA 5,048,096 09-10-2008 Beato BI-TONAL IMAGE NON- TEXT MATTER REMOVAL WITH RUN LENGTH AND CONNECTED COMPONENT ANALYSIS __________________________________________________________________________
The Russell patents ('481, '488, and '609) all generally relate to recording and playback systems, typically for use in connection with television broadcasting. The patents are related to one another and share quite a lot of common information. They are included for informational purposes since they each disclose "electronic means" wherein data is compressed while recording into lines and then expanded upon readout.
Dischert et al. and Jose et al. both relate to compression/expansion systems for use in connection with wide screen televisions. Both patents generally relate to "squeezing" the left and right edges of a wide screen image in order to make the image compatible with conventional television receivers. Pixels are deleted in accordance with defined pixel deletion patterns.
In general, Lee involves the identification of text and graphic zones within an image, and the compression of the identified text zones. Graphic zones are not compressed.
Whitehouse relates to a TV bandwidth reduction system using a hybrid discrete cosine transformer and a differential pulse modulator.
Murakami relates to an image information filing apparatus in which documents are recorded as image information on optical disks.
Hoque relates to a method and system which facilitate the processing of financial documents in banking systems.
Anderson ('834) relates to the printing and other processing of binary images, and more particularly to systems in which the images are comprised of non-coded digital information in the form of vectors of run lengths or run end positions representing lines of raster bits arranged in a given scan format or direction. Anderson ('786) relates to binary digital image processing methods and more particularly to improved methods for enlarging binary image data stored in run representation form.
Ara relates to an image signal-generating circuit which horizontally compresses dots which form an image pattern.
Ny relates to a file data retrieving system, and in particular to a file data retrieving system which can be suitably applied to a microcomputer system having a data filing function, such as electronic filing system and a work station.
Everett, Jr. relates to the field of image processing, and more particularly to digitally storing one or more selected scan lines from a composite video signal in real time.
Davy relates to methods and apparatus for modifying a digital representation of an image in which the digital data defines the content of pixels of the image.
Beato relates to pre-processing devices which remove non-text material from a text image for optical text character recognition systems which are capable of processing only text images.
Pawelski relates to apparatus for processing of component high-quality video signals at the transmitter and at the receiver of a video transmission system, and particularly concerns a differential pulse code modulation encoder and a decoder for such system.
The present invented method, apparatus and article of manufacture differ from the related art by, among other things, employing unique resizing and pixel averaging components.